/*
 * @(#)Tree.java
 *
 * Revision:
 * Author                                         Date           
 * --------------------------------------------   ------------   
 *  Jeremias D. Serafim de Araujo                     14/11/2012    
 */

package br.edu.ufcg.splab.core.graph;




import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.UUID;

import br.edu.ufcg.splab.core.InterfaceEdge;
import br.edu.ufcg.splab.core.InterfaceVertex;
import br.edu.ufcg.splab.core.edges.Edge;
import br.edu.ufcg.splab.core.edges.EdgeType;
import br.edu.ufcg.splab.core.vertex.Node;



/**
 *
 * A class that represents a tree,and contains collections 
 * of Node and edges, to establish its structure. Edges and 
 * Nodes are elements of the tree. A tree is a graph without loop.
 *  
 * Converting a graph to a tree, we detect the presence of loop 
 * when the vertex of the graph is visited for the second time, 
 * we generate subtrees that represent the loop, from the vertex
 * marked, and with the subtrees doing n expansions
 *	
 **/

public class Tree extends AbstractGraph {
	
	
	/**
	 * A map of the node of the tree.
	 * The key is the UUID and value is a node.
	 * this map has the vertices to union with subTrees
	 */
	private Map<UUID, Node> listVertexMarked;
	
	/**
	 *A map of the subTrees of the tree.
	 *The key is the label root of the subTree and value is a subTree
	 */
	//TODO  ESSA STRING AQUI VAI SER O KEYMARKED
	private Map<String, Tree> subTrees;
	
	
	/**
	 * Constructor
	 * Create a tree
	 */
	public Tree(){
		super();
		this.listVertexMarked = new HashMap<UUID, Node>();
		this.subTrees = new HashMap<String, Tree>();
	}
	/**
	 * 
	 * Adds a node in tree with specified label
	 * If node is a first this is a root of the tree
	 * Returns uuid because we need to create an edge,
	 * uuid Node from and uuid Node to
	 * 
	 * @param label is the label of node
	 * @return UUID
	 */
	public UUID addNode(String label){
		Node node = new Node(label);
		if(getStates().size()==0)
			setRoot(node);
		this.getStates().put(node.getUUID(), node);
		
		return node.getUUID();
	}
	

	
//	public void addEdge(UUID from,String label,UUID to){
//		InterfaceVertex nodeFrom = getStates().get(from);
//		InterfaceVertex nodevTo = getStates().get(to);
//		
//		if(nodeFrom==null || nodevTo==null){
//				//TODO axu q nao vai ter erro aqui.. pq ja teria dado erro la no graph
//			//throw new NullPointerException("State was not specified for edge");
//		}
//		//TODO IMPORTANTE AQUI... TIPO AQUI VAI SER DEFAULT
//		InterfaceEdge edge = new Edge(nodeFrom, label, nodevTo, Type.DEFAULT);
//		nodeFrom.addEdgeOutTransitions(edge);
//		nodevTo.addEdgeInTransitions(edge);
//		this.getEdges().add(edge);
//	}
	
	/**
	 * Create edge between the node specified with respective labelEdge
	 * and adds edge in tree
	 * @param from is the id of vertex from
	 * @param label is the label of the edge
	 * @param to is the id of vertex to
	 * 
	 */
	//TODO ana emilia mudou o retorno
	public InterfaceEdge addEdge(UUID from,String label,UUID to){
		InterfaceVertex nodeFrom = getStates().get(from);
		InterfaceVertex nodevTo = getStates().get(to);
		
		if(nodeFrom==null || nodevTo==null){
				//TODO axu q nao vai ter erro aqui.. pq ja teria dado erro la no graph
			//throw new NullPointerException("State was not specified for edge");
		}
		//TODO IMPORTANTE AQUI... TIPO AQUI VAI SER DEFAULT
		InterfaceEdge edge = new Edge(nodeFrom, label, nodevTo, EdgeType.DEFAULT);
		nodeFrom.addEdgeOutTransitions(edge);
		nodevTo.addEdgeInTransitions(edge);
		this.getEdges().add(edge);
		return edge;
	}
	
	
	
	/**
	 * Add a node in the listVertexMarkeds
	 * This listVertexMarked is used to identify the vertices in the collage of subtrees
	 * @param label is the uuid of Node
	 * @param node is the Node
	 * 
	 * */
	public void addNodeMarked(UUID label, Node node) {
		this.listVertexMarked.put(label, node);		
	}
	

	/**
	 * Adds subtrees in a map. This subtree will be conected to the tree.
	 * 
	 * @param subTree
	 */
	private void addSubTree(Tree subTree){
		this.subTrees.put(((Node) subTree.getRoot()).getKeyMarked(), subTree);
	
		//System.out.println(this.subTrees);
	}
	
	/**
	 * This method expands a tree. The
	 * number of expansions is defined.
	 * 
	 * 
	 * @param int n is the numer of expansion
	 */
	public void expand(int n){
		for(int i=0;i<n;i++){
			joining();
		}
		
	}
	
	/*
	 * Gets and Sets
	 * **/
	public Map<UUID, Node> getListVertexMarked(){
		return this.listVertexMarked;
	}
	private void setVertexMarked(Map<UUID, Node> newListVertexMarked) {
		this.listVertexMarked= newListVertexMarked;
	}
	public Map<String, Tree> getSubTrees(){
		return this.subTrees;
	}
	

	
	/**
	 * 
	 * It is responsible for creating the subtrees
	 * 
	 * @param node
	 * @param uuidVfrom
	 * @return tree is a subtree 
	 */
	//criamos a subarvore apartir do vertice especificado
	private Tree createSubTree(Node node, UUID uuidVfrom){
		Tree t = new Tree();
		dfsSubTree(node,uuidVfrom,t);
		return t;
	}

	
	/**
	 * It is responsible for creating copies of subtree,
	 * we do a dfs traditional starting vertex specified
	 * in the tree
	 * 
	 * @param node
	 * @param uuidFrom
	 * @param tree is the tree that will be copied
	 */
	//faz uma copia da estrutura
	private void dfsSubTree(Node node,UUID uuidFrom, Tree tree){
		
		if (uuidFrom == null) {
			uuidFrom = tree.addNode(node.getLabel());
		}
		for (InterfaceEdge edge : node.getOutTransitions()) {		
				Node nodeTo = (Node) edge.getTo();		
				UUID uuidvTo = tree.addNode(nodeTo.getLabel());
				InterfaceEdge newEdge = tree.addEdge(uuidFrom,edge.getLabel(),uuidvTo);
				newEdge.setType(edge.getType());
				
				//if tiver truee o cara add na lista de vertex marcados
				if( !nodeTo.getKeyMarked().equals("")){

					Node n = (Node) tree.getStates().get(uuidvTo);
					//System.out.println("vTo:"+vertexTo+"add o cara aqui e ele ta true");
					//n.setMarked(true);
					n.setKeyMarked(nodeTo.getKeyMarked());
					tree.addNodeMarked(uuidvTo, n);		
				}
				dfsSubTree(nodeTo, uuidvTo,tree);	
		} 
	}

	
	/**
	 *
	 *	Generate all subTrees of tree, if the tree has three 
	 * vertices marked, we will have 3 subtrees
	 *	
	 * */
	 public void generateSubTrees()  {
	
		Map<UUID, Node> lista = getListVertexMarked();
	
		for (Node v : lista.values()) {
			//if(!getSubTrees().containsKey(v.getLabel()) ){
				//System.out.println("%%%%%%%%%%%%%%%%%% 123.");
				//System.out.println(v);
				backTrack(v, v);
			//}
			//v.setMarked(false);
		}
	}

	
	 
	 /**
	  * Starting from the leaves marked in the tree, 
	  * climbed the tree to find a node with the same 
	  * label leaf marked, then creating a subtree starting 
	  * this node
	  * 
	  * @param nodeTo 
	  * @param nodeMarked is the vertex marked
	  */
	// apartir dos vertices folhas marcados nois subimos na arvore ate encontrar
	// um vertice com mesmo label, quando encontrado nois fazemos uma copia da
	// estrutura que esta abaixo
	private void backTrack(Node nodeTo, Node nodeMarked){//, Tree tree) {
		List<InterfaceEdge> listaArestas = nodeTo.getInTransitions();
		Node vFrom = (Node) listaArestas.get(0).getFrom();
		if (vFrom.getLabel().equals(nodeMarked.getLabel())) {
			Tree subTree = createSubTree(vFrom, null);// generate.createArvore
			((Node) subTree.getRoot()).setKeyMarked(nodeMarked.getKeyMarked());
//			System.out.println("CRIEI---------------TA");
//			System.out.println(subTree);
			addSubTree(subTree);
		} else {
			backTrack(vFrom, nodeMarked);
		}

	}
	
	
	
	/**
	 * Here we make a union between two trees,
	 * removes the root of the tree that will 
	 * be glued and update the lists of edges
	 * 
	 * @param nodeMarked
	 * @param subTree
	 */
	//responsavel por colar uma subarvore em determinado vertice
	private  void Union( InterfaceVertex nodeMarked, Tree subTree){
		InterfaceVertex root = getRoot();
		List<InterfaceEdge> edges =getEdges();
		edges.addAll(subTree.getEdges());
		Map<UUID,InterfaceVertex> states = getStates();
		states.putAll(subTree.getStates());

		for(InterfaceEdge edge: subTree.getRoot().getOutTransitions()){
			edge.setFrom(nodeMarked);
			nodeMarked.addEdgeOutTransitions(edge);
		}
		states.remove(subTree.getRoot().getUUID());
		setRoot(root);
		setEdges(edges);
		setStates(states);

	}
	
	
	/**
	 * Here we do apply the union in all marked
	 * node of the tree
	 * 
	 */
	//aqui nois colamos todas as subarvores na arvore
	private void joining() {
		
		Map<UUID, Node> newListNodeMarked = new HashMap<UUID, Node>();
		for (Node node : getListVertexMarked().values()) {
			Tree subTree = getSubTrees().get(node.getKeyMarked());
			//ConvertGraphToTree generate = new ConvertGraphToTree();
			Tree newSubTree =createSubTree((Node) subTree.getRoot(),null);// vai copiar o grafo com objetos != isso eh// custoso...COPIAR DE OUTRA FORMA

			newListNodeMarked.putAll(newSubTree.getListVertexMarked());
			//System.out.println("!!@!!>>"+newListVertexMarked);
			Union(node, newSubTree);
			node.setKeyMarked("");
		}

		setVertexMarked(newListNodeMarked);


	}


}
